package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.LinkedProblem;
import cn.pugle.oj.catalog.TwoProblem;
import cn.pugle.oj.catalog.Unknown;

/**
 * https://leetcode.com/problems/remove-nth-node-from-end-of-list/
 *
 * @author tzp
 * @since 2020/10/20
 */
public class LC19_1 implements TwoProblem, LinkedProblem {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || head.next == null) return null;
        ListNode slow = head, fast = head;
        int i = 1;
        while (i <= n) {
            fast = fast.next;
            i++;
        }//移动n次, 现在fast是正数第n+1;
        if (fast == null) return head.next;//注意这里, 特判的是n==length, 即移除head的情况
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }//现在slow是倒数第n+1个;
        slow.next = slow.next.next;
        return head;
    }

    public static void main(String[] args) {
        System.out.println(new LC19_1().removeNthFromEnd(
                ListNode.arrayToListNode(new int[]{1, 2, 3, 4, 5}), 1));
        System.out.println(new LC19_1().removeNthFromEnd(
                ListNode.arrayToListNode(new int[]{1, 2, 3, 4, 5}), 2));
        System.out.println(new LC19_1().removeNthFromEnd(
                ListNode.arrayToListNode(new int[]{1, 2, 3, 4, 5}), 3));
        System.out.println(new LC19_1().removeNthFromEnd(
                ListNode.arrayToListNode(new int[]{1, 2, 3, 4, 5}), 4));
        System.out.println(new LC19_1().removeNthFromEnd(
                ListNode.arrayToListNode(new int[]{1, 2, 3, 4, 5}), 5));
    }
}
